// @algorithm @lc id=2040 lang=cpp 
// @title minimum-cost-to-reach-destination-in-time


// #define print(...)
// @test(30,[[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]],[5,1,2,20,20,3])=11
// @test(29,[[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]],[5,1,2,20,20,3])=48
// @test(25,[[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]],[5,1,2,20,20,3])=-1
#define INF (INT_MAX>>1)
class Solution {
public:
    int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
        int n = passingFees.size();
        vector<vector<int>> dp(maxTime+1, vector<int>(n+1, INF));
        dp[0][0] = passingFees[0];
        for(int t=1; t<=maxTime; t++){
            for(auto & e : edges){
                int spend = e[2];
                if(t < spend) continue;
                int c1 = e[0], c2 = e[1];
                dp[t][c1] = min(dp[t][c1], dp[t-spend][c2] + passingFees[c1]);
                dp[t][c2] = min(dp[t][c2], dp[t-spend][c1] + passingFees[c2]);
            }
        }
        int ans = INF;
        for(int t=1; t<=maxTime; t++)
            ans = min(ans, dp[t][n-1]);
        return ans==INF?-1:ans;
    }
};